1. Field of the Invention
The present invention relates generally to a communication system using a Low-Density Parity Check (LDPC) code, and more particularly, to a channel encoding/decoding method and apparatus for supporting various codeword lengths or code rates using a given LDPC code.
2. Description of the Related Art
In wireless communication systems, link performances are significantly degraded by various noises, fading of channels, and Inter-Symbol Interference (ISI). Therefore, to realize high-speed digital communication systems requiring high data throughput and reliability, such as a next-generation mobile communication system, a digital broadcasting system, and a mobile Internet system, it is important to develop technologies for coping with the noises, fading, and ISI. Recently, error-correcting codes have been studied for improving communication reliability by efficiently restoring information distortion.
An LDPC code, which was first introduced as a typical example of the error-correcting code by Gallager in 1960s, has been long forgotten due to its implementation complexity far exceeding the then technology. However, the LDPC code was restudied in late 1990s, proving that the LDPC code has performance close to Shannon's channel capacity, if decoded by sum-product algorithm-based iterative decoding on a Tanner graph corresponding to the LDPC code. Therefore, the LDPC code is now again being used or considered for use in various systems.
The LDPC code can be commonly defined by a parity check matrix, and can be represented using a bipartite graph called a Tanner graph. The bipartite graph includes two different types of vertexes, which are called variable nodes and check nodes. The variable nodes correspond to encoded bits on a one-to-one basis, and the check nodes represent algebraic relationships between the encoded bits.
FIG. 1 illustrates an example of a parity check matrix H1 of an LDPC code having four rows and eight columns. Referring to FIG. 1, the parity check matrix H1 generates a codeword with a length of 8, because it has eight columns.
FIG. 2 illustrates a Tanner graph corresponding to the parity check matrix H1 of the LDPC code, as illustrated in FIG. 1.
Referring to FIG. 2, the Tanner graph includes eight variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216, and four check nodes 218, 220, 222, and 224. An i-th column and a j-th row in the parity check matrix H1 correspond to a variable node xi and a j-th check node, respectively. A value of 1, i.e., a non-zero value, at the point where an i-th column and a j-th row cross in the parity check matrix H1 indicate that an edge exists between the variable node xi and the j-th check node on the Tanner graph, as illustrated in FIG. 2.
In the Tanner graph, a degree of each of the variable nodes and the check nodes means the number of edges connected thereto, and is identical to the number of entries, which are not zero (0) in columns or rows corresponding to their associated nodes in the parity check matrix. For example, in FIG. 2, degrees of the variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216 are 4, 3, 3, 3, 2, 2, 2, and 2, respectively, and degrees of the check nodes 218, 220, 222, and 224 are 6, 5, 5, and 5, respectively. As mentioned above, the number of non-zero entries in columns in the parity check matrix H1 of FIG. 1, which correspond to the variable nodes of FIG. 2, are equal to the above degrees 4, 3, 3, 3, 2, 2, 2, and 2 in order, and the number of non-zero entries in rows in the parity check matrix H1 of FIG. 1, which correspond to the check nodes of FIG. 2, are identical to the above degrees 6, 5, 5, and 5 in order.
To represent a degree distribution for nodes of an LDPC code, it is assumed that a ratio of the number of variable nodes with a degree i to the total number of variable nodes is represented by fi and a ratio of the number of check nodes with a degree j to the total number of check nodes is represented by gj. For example, for the LDPC code corresponding to FIGS. 1 and 2, f2=4/8, f3=3/8, and f4=1/8, and fi=0 for i≠2, 3, 4; and g5=3/4 and g6=1/4, and gj=0 for j≠5, 6. Assuming that a length (i.e., the number of columns) of an LDPC code is N and the number of rows is N/2, a density of non-zero entries in the entire parity check matrix having the above degree distribution is calculated using Equation (1) below.
                                                        2              ⁢                              f                2                            ⁢              N                        +                          3              ⁢                              f                3                            ⁢              N                        +                          4              ⁢                              f                4                            ⁢              N                                            N            ·                          N              /              2                                      =                  5.25          N                                    (        1        )            
In Equation (1), increasing N decreases the density of a weight of 1 in the parity check matrix. For an LDPC code, because its length N is inverse proportional to the density of non-zero entries, an LDPC code with a large N has a very low density of non-zero entries. The phrase ‘low density’ in the name LDPC code was derived from this principle.
FIG. 3 is a diagram illustrating a conventional LDPC encoding process.
Referring to FIG. 3, the number of bits input to an LDPC encoder 310 is, for example, K1=16, and information bits are represented as, for example, u={u0, u1, . . . , u15}. Herein, the bits input to the LDPC encoder 310 will be referred to individually as information bits or collectively as an information word.
The LDPC encoder 310 generates parity bits, and generates an LDPC codeword c=(u, p) by adding the generated parity bits to the input information bits as illustrated in FIG. 3. A process in which the LDPC encoder 310 adds parity bits to information bits using the parity check matrix is referred to as an LDPC encoding process.
Because an LDPC code is defined by a parity check matrix, a given system stores the parity check matrix in order to apply the LDPC code. Generally, to store an LDPC code, position information of a weight of 1 in the parity check matrix is stored. However, because a codeword length of an LDPC code used in the actual system ranges from hundreds of bits to hundreds of thousands of bits, the memory required to store the position information of a weight of 1 can become very large in capacity if the codeword length of the LDPC code is very long.
To overcome these shortcomings, many studies have been conducted on LDPC codes with various parity check matrixes having specific structures. For a parity check matrix having a specific structure, because positions of a weight of 1 are limited in its parity check matrix according to a specific condition, the positions of a weight of 1 can be stored more efficiently.
FIG. 4 is a diagram illustrating a parity check matrix having the specific structure.
Referring to FIG. 4, N1 represents a length of an LDPC codeword, which is equal to a length of its parity check matrix. K1 represents a length of an information word (or the number of information bits), which is equal to a length of an information part of the parity check matrix, and (N1−K1) represents a length of parity bits, which is equal to a length of a parity part of the parity check matrix. Integers M1 and q are determined so as to meet q=(N1−K1)/M1. K1/M1 is also an integer.
In the parity check matrix of FIG. 4, positions of a weight of 1 in a K1-th column to an (N1−1)-th column, which are a part corresponding to the parity bits, have a dual diagonal structure. Therefore, it can be understood that degrees of columns corresponding to the parity bits are all 2, except for a degree of the (N1−1)-th column, which is 1.
Referring to FIG. 4, in the parity check matrix, a structure of a 0-th column to a (K1−1)-th column, which corresponds to an information part, can be made according to the following rules:
Rule 1: In the parity check matrix, a total of K1/M1 column groups are generated by grouping K1 columns corresponding to an information word into a plurality of groups each including M1 columns. Columns in each column group are generated according to Rule 2 below.
Rule 2: First, positions of 1 in a 0-th column in an i-th (i=1, . . . , K1/M1) column group are determined. Second, assuming that a degree of a 0-th column in each i-th column group is represented by Di, if positions of rows with 1 are Ri,0(1), Ri,0(2), . . . , Ri,0(Di) then positions Ri,j(k) (k=1, 2, . . . , Di) of rows with 1 in a j-th (j=1, 2, . . . M1−1) column in an i-th column group are defined as shown in Equation (2) below.Ri,j(k)=Ri,(j-1)(k)+q mod(N1−K1) k=1,2, . . . ,Di, i=1, . . . ,K1/M1, j=1, . . . ,M1−1  (2)
According to Rules 1 and 2, it is noted that degrees of columns in an i-th (i=1, . . . , K1/M1) column group are all equal to Di. Now,
As a more detailed example, for N1=30, K1=15, M1=5 and q=3, position information of rows with 1 in a 0-th column in each of three column groups may be represented in the following three sequences. These sequences are referred to as “weight-1 position sequences”.R1,0(1)=1, R1,0(2)=2, R1,3(3)=8, R1,0(4)=10,R2,0(1)=0, R2,0(2)=9, R2,0(3)=13,R3,0(1)=0, R3,0(2)=14.
As to the weight-1 position sequences for positions of rows with 1 in a 0-th column in each column group, only their sequences are also represented on a column group basis as follows, for convenience.                1 2 8 10        0 9 13        0 14        
That is, the i-th weight-1 position sequence sequentially represents position information of rows with 1 in an i-th column group.
FIG. 5 is a diagram illustrating an example of a parity check matrix of an LDPC code. Specifically, the parity check matrix illustrated in FIG. 5 is generated by constructing a parity check matrix using the information corresponding to the above detailed example, and Rules 1 and 2.
To apply an LDPC code to an actual communication system, the LDPC code should be generated in consideration of a required data rate in the communication system. In particular, not only in an adaptive communication system employing Hybrid Automatic Retransmission Request (HARD) and Adaptive Modulation and Coding (AMC), but also in a communication system supporting various broadcast services, LDPC codes having various codeword lengths are required to support various data rates required by the systems.
However, in order to support LDPC codes having various codeword lengths or code rates, a high-capacity memory is required to store parity check matrixes corresponding to different codeword lengths or code rates. In particular, an increase in the number of types of the supported codeword lengths or code rates also lead to an increase in the required memory capacity, thereby reducing the system efficiency. Therefore, there is a need for more efficiently supporting a variety of codeword lengths or code rates using a given, existing parity check matrix, without generating new parity check matrixes corresponding to different codeword lengths or code rates.